You're not currently signed in.
Sign in »
Numerical Analysis (CS 450) Spring 2018
| What | Where |
|---|---|
| Time/place | WF 1:00pm-2:15pm 1404 Siebel / Catalog |
| Class URL | https://relate.cs.illinois.edu/course/cs450-s18/ |
| Class recordings | View Echo 360 Video » |
| Web forum | View Piazza » |
| Calendar | View Calendar » |
Quizzes
The latest five quizzes will be posted below. To access all previous quizzes, go to (Participant, View Grades, follow desired flow grade link, follow arrow flow link),
Quiz 28: Methods for Solving Sparse Linear Systems »
Quiz 27: Numerical Methods for PDEs »
Quiz 26: Methods for Solving ODE BVPs »
Exams
Please find information on our upcoming exams in the corresponding section of the class calendar. Reserve your time slots in the testing facility as soon as possible--otherwise your preferred times may no longer be available.
Homework
Homeworks will be posted here generally on a biweekly basis. They will usually be due at 10 pm Thursdays.
Homework 7 » 4 Credit-Hour Addendum to Homework 7 »
Homework 6 » 4 Credit-Hour Addendum to Homework 6 »
Homework 5 » 4 Credit-Hour Addendum to Homework 5 »
Homework 4 » 4 Credit-Hour Addendum to Homework 4 »
Homework 3 » 4 Credit-Hour Addendum to Homework 3 »
Homework 2 » 4 Credit-Hour Addendum to Homework 2 »
Homework 1 » 4 Credit-Hour Addendum to Homework 1 »
Assignments for 4 Credit-Hour Section
If you are enrolled in CS 450 for 4 credit hours, you will need to complete (typically one) additional question along with each homework assignments. Registration for the section has been opened for undergraduates as well. Students enrolled in the 3 credit hour section can complete the additional problems for some extra credit points.
Course Outline
-
1. Chapter 1: Scientific Computing
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 1: Policies
- Lecture 2 Activity: Cancellation in Standard Deviation Computation
- Recitation 1 Activity: Finite Difference Computational Error
- Quiz 2: Error, Conditioning, and Floating Point
- Demo: Catastrophic Cancellation
- Demo: Conditioning of Evaluating tan
- Demo: Density of Floating Point Numbers
- Demo: Floating Point and the Series for the Exponential Function
- Demo: Floating Point vs Program Logic
- Demo: Floating point and the Harmonic Series
- Demo: Picking apart a floating point number
- Demo: Polynomial Evaluation Floating Point
- Demo: Truncation vs Rounding
- Demo: Vector Norms
-
2. Chapter 2: Systems of Linear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Lecture 3 Activity: Matrix Norms and Conditioning
- Quiz 3: Floating Point, Norms, and Matrices
- Lecture 4 Activity: Singular Value Decomposition and Norms
- Quiz 4: Matrix Conditioning and Error in Linear Systems
- Recitation 2 Slides: Linear Algebra Review
- Lecture 5 Notes: Solving Linear Systems
- Lecture 5 Activity: LU Factorization using Elementary Matrices
- Quiz 5: Gaussian Elimination
- Recitation 2 Slides: Linear Algebra Review
- Demo: Coding back-substitution
- Demo: Complexity of Mat-Mat multiplication and LU
- Demo: Condition number visualized
- Demo: Conditioning of 2x2 Matrices
- Demo: Elimination Matrices I
- Demo: Elimination Matrices II
- Demo: LU factorization
- Demo: LU with Partial Pivoting
- Demo: Matrix norms
- Demo: Sherman-Morrison
- Demo: Vanilla Gaussian Elimination
-
3. Chapter 3: Linear Least Squares
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 6: Linear Least Squares
- Lecture 7 Activity: QR Iteration with Shift
- Quiz 7: Cost and Stability of Least Squares Algorithms
- Demo: 3x3 Givens demo
- Demo: 3x3 Householder demo
- Demo: Gram-Schmidt and Modified Gram-Schmidt
- Demo: Gram-Schmidt--The Movie
- Demo: Image compression
- Demo: Interactive Polynomial Fit
- Demo: Issues with the normal equations
- Demo: Keeping track of coefficients in Gram-Schmidt
- Demo: Normal equations vs Pseudoinverse
- Demo: Polynomial fitting with the normal equations
- Demo: Relative cost of matrix factorizations
-
4. Chapter 4: Eigenvalue Problems
- Notes (Michael T. Heath)
- Lecture Notes
- Lecture 8 Activity: Inverse Iteration with a Shift
- Quiz 8: Basics of Eigenvalue Problems
- Lecture 9 Activity: Schur Form and Eigenvectors
- Quiz 9: Solving Eigenvalue Problems by Similarity Transformations
- Quiz 10: Sensitivity of Eigenvalue Problems and Krylov Subspace Methods
- Quiz 11: Methods and Properties of Eigenvalue Problems
- Quiz 12: Feedback Survey
- Demo: Arnoldi iteration with complex eigenvalues
- Demo: Arnoldi iteration
- Demo: Arnoldi vs Power Itation
- Demo: Householder Similarity Transforms
- Demo: Orthogonal Iteration
- Demo: Power iteration and its Variants
- Demo: Rounding in characteristic polynomial using SymPy
-
5. Chapter 5: Nonlinear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 13: Methods for 1D Nonlinear Equations
- Lecture 14 Activity: Newton's Method with Finite Differences
- Quiz 14: Newton's Method for Systems of Nonlinear Equations
- Demo: Bisection Method
- Demo: Convergence of Newton's Method
- Demo: Convergence of the Secant Method
- Demo: Fixed point iteration
- Demo: Newton's Method
- Demo: Newton's method in n dimensions
- Demo: Rates of Convergence
- Demo: Secant Method
- Demo: Three quadratic functions
- Code: three-quadratics.py
-
6. Chapter 6: Optimization
- Notes (Michael T. Heath)
- Lecture Notes
- Lecture 15 Activity: Optimization
- Quiz 15: Broyden's Method and Basics of Optimization
- Lecture 16 Activity: Optimization Algorithms
- Quiz 16: Algorithms for Unconstrained Numerical Optimization
- Lecture 17 Activity: Constrained Optimization Algorithms
- Quiz 17: Constrained Optimization Methods
- Lecture 18 Activity: Optimization with Krylov Methods
- Quiz 18: Conjugate Gradient and Constrained Numerical Optimization
- Demo: Gauss-Newton
- Demo: Golden Section Proportions
- Demo: Nelder-Mead Method
- Demo: Newton's Method in 1D
- Demo: Newton's Method in n dimensions
- Demo: Sequential Quadratic Programming
- Demo: Steepest Descent
-
7. Chapter 7: Interpolation
- Notes (Michael T. Heath)
- Lecture Notes
- Lecture 19 Activity: Interpolation
- Quiz 19: Basics of Interpolation
- Lecture 20 Activity: Chebyshev Interpolation
- Quiz 20: Orthogonal and Piecewise Interpolation
- Demo: Chebyshev interpolation
- Demo: Choice of Nodes for Polynomial Interpolation
- Demo: Composite Gauss Interpolation Error
- Demo: Interpolation Error
- Demo: Interpolation with Radial Basis Functions
- Demo: Jump with Chebyshev Nodes
- Demo: Monomial interpolation
- Demo: Orthogonal Polynomials
-
8. Chapter 8: Numerical Integration and Differentiation
- Notes (Michael T. Heath)
- Lecture Notes
- Lecture 21 Activity: Computing Quadrature Weights
- Quiz 21: Basic Numerical Quadrature
- Quiz 22: Numerical Quadrature and Differentiation
- Demo: Accuracy of Newton-Cotes
- Demo: Finite Differences vs Noise
- Demo: Floating point vs Finite Differences
- Demo: Gaussian quadrature weight finder
- Demo: Newton-Cotes weight finder
- Demo: Richardson with Finite Differences
- Demo: Taking Derivatives with Vandermonde Matrices
-
9. Chapter 9: Initial Value Problems for ODEs
- Notes (Michael T. Heath)
- Lecture Notes
- Lecture 23 Activity: Ordinary Differential Equations
- Quiz 23: Introduction to Ordinary Differential Equations
- Lecture 24 Activity: Heun's Method
- Quiz 24: Numerical Solutions to ODE IVPs
- Demo: Backward Euler stability
- Demo: Dissipation in Runge-Kutta Methods
- Demo: Forward Euler stability
- Demo: Stability regions
- Demo: Stiffness
- 10. Chapter 10: Boundary Value Problems for ODEs
-
11. Chapter 11: Partial Differential Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 27: Numerical Methods for PDEs
- Quiz 28: Methods for Solving Sparse Linear Systems
- Demo: Conjugate Gradient Method
- Demo: Jacobi vs Conjugate Gradient
- Demo: Sparse Matrix Factorizations and Fill-In
- Demo: Stationary Iterative Methods
- Demo: Time-dependent PDEs
- 12. Chapter 12: Fast Fourier Transform
- 13. Chapter 13: Random Numbers and Simulation
Team
Textbook
Scientific Computing: An Introductory Survey
Michael T. Heath, Second Edition, McGraw-Hill.
Computing
We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments. No other languages are permitted. Python has a very gentle learning curve, so you should feel at home even if you've never done any work in Python.
Virtual Machine Image
While you are free to install Python and Numpy on your own computer to do homework, the only supported way to do so is using the supplied virtual machine image.
Grading Policies
Previous Editions of CS 450
Additional Text Resources
- Linear Algebra and Its Applications Gilbert Strang, 4th Edition, Harcourt Brace, 1987 (on reserve at Grainger).
- Numerical Linear Algebra Lloyd Trefethen and David Bau, SIAM, 1997 (on reserve at Grainger).
- Applied Numerical Linear Algebra James Demmel, SIAM, 1997.
- Matrix Computations Gene Golub and Charles Van Loan, 4th Edition, The John's Hopkins University Press, 2013.
- Numerical Recipes William Press, Saul Teukolsky, William Vetterling, and Brian Flannery, 3rd Edition, Cambridge University Press, 2007.
Python Help
(see section 1 of the outline for more)
- Python tutorial
- Facts and myths about Python names and values
- Learn Python the hard way
- Project Euler (Lots of practice problems)
Python Workshop Material
- Video: Located on Echo 360 along with the other class recordings
- Tutorial material
- Scipy lecture notes
- CSE workshop training material
Numpy Help
(see section 1 of the outline for more)
- Introduction to Python for Science
- The SciPy lectures
- The Numpy MedKit by Stéfan van der Walt
- The Numpy User Guide by Travis Oliphant
- Numpy/Scipy documentation
- More in this reddit thread
- Spyder (a Python IDE, like Matlab) is installed in the virtual machine. (Applications Menu > Development > Spyder)
- An introduction to Numpy and SciPy